// SLinkList 单项不循环链表
// 不带头结点
// 与顺序表相比，增容不会浪费
// 且效率高，体现在插入删除时间复杂度为O(1)
// 形参只是实参的一个拷贝,其改变对实参无影响

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SListNode;

SListNode* BuySListNode(SLTDataType val);

void SListPushBack(SListNode** ppHead, SLTDataType val);
void SListPushFront(SListNode** ppHead, SLTDataType val);
void SListPopBack(SListNode** ppHead, SLTDataType val);
void SListPopFront(SListNode** ppHead);

SListNode* SListFind(SListNode* pHead, SLTDataType val);
void SListPrint(SListNode* pHead);
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType val);
void SListErase(SListNode** ppHead, SListNode* pos);

// 申请一个链表结点的内存
SListNode* BuySListNode(SLTDataType val)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    newNode->data = val;
    newNode->next = NULL;

    return newNode;
}

void SListPushBack(SListNode** ppHead, SLTDataType val)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    newNode->data = val;
    newNode->next = NULL;

    if (*ppHead == NULL){
        *ppHead = newNode;
    }
    else {
        // 找尾结点的指针
        SListNode* tail = *ppHead;
        while (tail->next != NULL){
            tail = tail->next;
        }
        // 链接新结点
        tail->next = newNode;
    }
}

void SListPushFront(SListNode** ppHead, SLTDataType val)
{
    SListNode* newNode = BuySListNode(val);

    newNode->next = *ppHead;
    *ppHead = newNode;
}

void SListPopBack(SListNode** ppHead, SLTDataType val)
{
    // 若链表为空
    if (*ppHead == NULL){
        return ;
    }
    // 若链表只有一个结点
    else if ((*ppHead)->next == NULL){
        free(*ppHead);
        *ppHead = NULL;
    }
    else {
        SListNode *prev = NULL;
        SListNode *tail = *ppHead;

        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }

        free(tail);
        prev->next = NULL;
    }
}

void SListPopFront(SListNode** ppHead)
{
    SListNode* next = (*ppHead)->next;
    free(*ppHead);
    *ppHead = next;
}

void SListPrint(SListNode* pHead)
{
    SListNode* cur = pHead;

    while (cur != NULL){
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SListNode* SListFind(SListNode* pHead, SLTDataType val)
{
    SListNode* cur = pHead;

    while (cur != NULL){
        if (cur->data == val){
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

// 在pos的前面插入val
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType val)
{
    if (pos == *ppHead){
        SListPushFront(ppHead, val);
    }
    else {
        SListNode* newNode = BuySListNode(val);
        SListNode* prev = *ppHead;
        while (prev->next != pos){
            prev = prev->next;
        }
        prev->next = newNode;
        newNode->next = pos;
    }
}

// 删除pos位置的值
void SListErase(SListNode** ppHead, SListNode* pos)
{
    if (pos == *ppHead){
        SListPopFront(ppHead);
    }
    else {
        SListNode* prev = *ppHead;
        while (prev->next != pos){
            prev = prev->next;
        }

        prev->next = pos->next;

        free(pos);
        pos = NULL;
    }
}

int main(void)
{
    // 初始化
    SListNode* pHead = NULL;

    // 尾插
    SListPushBack(&pHead, 1);
    SListPushBack(&pHead, 2);
    SListPushBack(&pHead, 3);
    SListPrint(pHead);

    // 查找
    SListNode* pos = SListFind(pHead, 1);
    if (pos != NULL){
        printf("已找到，前面插入数字4，现为:\n");
        SListInsert(&pHead, pos, 4);
        SListPrint(pHead);

        SListErase(&pHead, pos);
        printf("已删除，现为:\n");
        SListPrint(pHead);
    }
    return 0;
}
























